A very important and challenging problem in the design of high-speed communication networks is that of providing Quality of Service (QoS) guarantees, usually specified in terms of loss probabilities or packet delays in the network. For example, the control of packet delays is often of crucial importance, particularly for real-time applications such as video delivery systems, wireless networks, multimedia networks, call centers, etc. A basic decision that has to be made in such contexts is that of connection admission control, i.e., one has to determine when a new user can be admitted to the system, while still fulfilling the QoS requirements of all users already in the system. Moreover, users already in the system have to be scheduled in the most efficient manner so as to maximize the number of users that can be admitted.
Exemplary admission control and scheduling techniques are disclosed in U.S. Pat. No. 5,838,663, issued Nov. 17, 1998 in the name of inventors A. Elwalid, D. Mitra and R. H. Wentworth and entitled “Method for Admission Control and Routing by Allocating Network Resources in Network Nodes,” which is incorporated by reference herein. For example, this patent discloses a technique that may be utilized in an admission control element of a router, switch or other network processing element to determine the maximum number of connections that can be admitted, for a given buffer size, without introducing undue amounts of loss or delay in the network traffic. However, in certain circumstances it is possible that this technique may substantially underestimate the maximum number of admissible connections, e.g., in the case of large buffer sizes. A need therefore exists for improved techniques which can provide a better estimate of the maximum number of admissible connections.
In addition, with regard to the problem of resource allocation, it is well known that there is a tradeoff between bandwidth and buffer space. More particularly, an input that is fed to a network link having unlimited bandwidth capacity requires zero buffer space and vice versa. However, conventional techniques have been unable to determine in an efficient manner the optimum tradeoff between bandwidth and buffer space. It would therefore also be desirable if improved techniques were available for determining this tradeoff. Such techniques could be used, for example, in network configuration, in the above-noted admission control, as well as in the scheduling of users already admitted to a network.